package com.qcby.demo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用双队列实现栈
 * 栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构
 */
public class StackUsingTwoQueues {
    // 两个队列，用于存储栈中的元素。
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    private int top; // 记录栈顶元素的值

    // 初始化 queue1 和 queue2 为 LinkedList 实例。
    public StackUsingTwoQueues() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    // 将新元素 x 添加到非空的队列中。
    public void push(int x) {
        // 如果 queue1 非空，则将 x 添加到 queue1；否则添加到 queue2。
        if (!queue1.isEmpty()) {
            queue1.add(x);
        } else {
            queue2.add(x);
        }
        top = x;  // 更新 top 为新元素的值。
    }

    // 检查栈是否为空，如果为空则抛出异常。
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈是空的。");
        }

        // 确定 nonEmptyQueue（非空队列）和 emptyQueue（空队列）。
        Queue<Integer> nonEmptyQueue = queue1.isEmpty() ? queue2 : queue1;
        Queue<Integer> emptyQueue = queue1.isEmpty() ? queue1 : queue2;

        // 将 nonEmptyQueue 中的所有元素（除了最后一个）移动到 emptyQueue 中，并更新 top。
        while (nonEmptyQueue.size() > 1) {
            top = nonEmptyQueue.remove();
            emptyQueue.add(top);
        }

        // 返回 nonEmptyQueue 中的最后一个元素（即栈顶元素）。
        return nonEmptyQueue.remove();
    }

    // 检查栈是否为空，如果为空则抛出异常。
    public int top() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top;  // 返回 top 变量的值（即栈顶元素）。
    }

    // 检查两个队列是否都为空，如果都为空则返回 true，否则返回 false
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

    public static void main(String[] args) {
        // 创建 StackUsingTwoQueues 实例 stack
        StackUsingTwoQueues stack = new StackUsingTwoQueues();
        // 调用 push 方法将元素 1、2、3 压入栈中。
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 调用 top 方法获取栈顶元素并打印（应为 3）。
        System.out.println("栈顶元素: " + stack.top()); // 3
        // 调用 pop 方法弹出栈顶元素并打印（应为 3）。
        System.out.println("弹出栈顶元素: " + stack.pop()); // 3
        // 再次调用 top 方法获取栈顶元素并打印（应为 2）。
        System.out.println("获取当前的栈顶元素: " + stack.top()); //  2
        // 调用 isEmpty 方法检查栈是否为空并打印（应为 false）。
        System.out.println("栈是空的吗? " + stack.isEmpty()); //  false
    }
}
